Independent transversals in graphs
Tomáš Kaiser

Abstract

Let G be a graph with a partition P of its vertex set. An independent
transversal in G (with respect to P) is an independent set of G
intersecting each class of P. Independent transversals have natural
connections to a variety of problems, and since 1970s, conditions for
their existence have been widely studied. We will discuss topological
and probabilistic arguments used to establish such conditions, as well
as recent developments related to the entropy compression
method. Includes joint work with Carla Groenland, Matt Wales and Oscar
Treffers.